New labeling techniques are provided for accelerating the basis exchange step of specialized linear programming methods for network problems. Computational results are presented which show that these techniques substantially reduce the amount of computation involved in updating operations. (Author)